package com.douma.practical_3.bitmap;

/**
 * 抖码课堂，专注中国程序员基础内功修炼
 * 官网：douma-tech.com
 * 公众号：资深程序员老汤
 *
 * @作者 : 老汤
 */
public class BitMap {

    // 位图，使用 byte 数组来实现，一个 byte 等于 8 个位
    private byte[] data;

    // 位图的大小
    private int size;

    public BitMap(int size) {
        this.size = size;
        // 比如申请的 size = 10，那么需要两个 byte
        // (10 + 7) / 8 = 2
        // +7 的目的：向上凑足一个 byte
        this.data = new byte[(size + 7) / 8];
    }


    /**
     * 将索引 num 的位设置为 1
     * 时间复杂度：O(1)
     * @param num
     */
    public void set(int num) {
        if (num >= size) return;

        int byteIndex = num / 8;
        byte b = data[byteIndex];

        int bitIndex = 7 - num % 8;

        data[byteIndex] = (byte) (b | (1 << bitIndex));

    }

    /**
     * 判断指定索引 num 对应的位是否是 1
     * 时间复杂度：O(1)
     * @param num
     * @return
     */
    public boolean test(int num) {
        if (num >= size) return false;

        int byteIndex = num / 8;
        byte b = data[byteIndex];

        int bitIndex = 7 - num % 8;

        return (b & (1 << bitIndex)) != 0;
    }

    public static void main(String[] args) {
        BitMap bitMap = new BitMap(100);

        bitMap.set(10);
        bitMap.set(88);
        bitMap.set(99);

        System.out.println(bitMap.test(33));
    }
}
